[[# Arithmetic circuits

2.1 Encoding the trace as arithmatic constraints

R1CS

• **Flattening：将电路的执行转换成计算轨迹，**即将复合函数以乘法为基本单元拆解成一组有序的简单函数$‘\{constrain{t}_1,\dots ,constrain{t}_n\}‘$，其中
  • $‘constrain{t}_i:=w_i=(u_{i1}+\dots +u_{it})\ast (v_{i1}+\dots +v_{iv})‘$, $‘w_i‘$为输出变量，$‘\{u_1,\dots ,u_n\}‘$为左输入变量，$‘\{v_1,\dots ,v_m\}‘$为右输入变量
  • 这里的有序是指按电路执行的顺序
  • 这里会引入中间变量$‘\{sym1,\dots ,symk\}‘$
    • 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量$‘sym\_i‘$
    • 除了叶子节点处的门之外，其他的门的输入引脚添加中间变量$‘sym\_i‘$，该中间变量来自于另一个门的输出
    • 举例说明：若门A的输出引脚接入到门B的输入引脚，则为门A的输出引脚和门B的输入引脚添加同一个中间变量$‘sym\_i‘$
• 重组$‘\{constraints\}‘$中的数据：将其变成一阶约束系统R1CS：$‘W\cdot \vec{a}=U\cdot \vec{a}\circ V\cdot \vec{a}‘$(注：$‘\circ ‘$ 为Hadamard product，按位乘法):
  • $‘\vec{a}:=\{one\}+\{out\}+\{x_1,\dots ,x_h\}+\{sym1,\dots ,symk\}‘$，即由表示1的冗余变量，函数输出，输入变量，中间变量构成的集合对应的向量。
  • $‘W:=\{constrain{t}_1,\dots ,constrain{t}_n\}‘$的输出变量基于$‘\vec{a}‘$的选择向量构成的矩阵
  • $‘U:=\{constrain{t}_1,\dots ,constrain{t}_n\}‘$的左输入变量基于$‘\vec{a}‘$的选择向量构成的矩阵
  • $‘V:=\{constrain{t}_1,\dots ,constrain{t}_n\}‘$的右输入变量基于$‘\vec{a}‘$的选择向量构成的矩阵
• 注：矩阵的行数等于乘法门的数量，矩阵的列数等于$‘\vec{a}‘$中元素的数量，即变量的数量

Plonkish Arithmetization

• **Flattening：**即将复合函数拆解成一组离散的门$‘\{constrain{t}_1,\dots ,constrain{t}_n\}‘$，其中
  • $‘constrain{t}_i:=q_{Oi}{w}_i=q_{Li}{u}_i+q_{Ri}{v}_i+q_{Mi}{u}_i{v}_i+q_{Ci}{c}_i‘$， $‘w_i‘$为输出变量，$‘u_i‘$为左输入变量，$‘v_i‘$为右输入变量，$‘c_i‘$为常量，$‘q_{Oi}‘$为输出选择器，$‘q_{Li}‘$为左输入变量选择器，$‘q_{Ri}‘$为右输入变量选择器，$‘q_{Mi}‘$为乘积选择器，$‘q_{Ci}‘$为常数选择器
  • **注：**矩阵的行数等于所有门的数量，即约束的数量，n。
  • 这里的有序是指计算的顺序
  • 这里会引入中间变量$‘\{sym1,\dots ,symk\}‘$
    • 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量$‘sym\_i‘$
    • 除了叶子节点处的门之外，其他的门的输入引脚添加中间变量$‘sym\_i‘$，该中间变量来自于另一个门的输出
    • 举例说明：若门A的输出引脚接入到门B的输入引脚，则为门A的输出引脚和门B的输入引脚添加同一个中间变量$‘sym\_i‘$
• **重组$‘\{constrain{t}_1,\dots ,constrain{t}_n\}‘$中的数据：**将其变成：$‘\overrightarrow{q_O}\circ \vec{w}=\overrightarrow{q_L}\circ \vec{u}+\overrightarrow{q_R}\circ \vec{v}+\overrightarrow{q_M}\circ (\vec{u}\circ \vec{v})+\overrightarrow{q_C}‘$(注：$‘\circ ‘$ 为Hadamard product，按位乘法)
  • $‘Q:=\{\overrightarrow{q_O},\overrightarrow{q_L},\overrightarrow{q_R},\overrightarrow{q_M},\overrightarrow{q_C}\}‘$，即选择器矩阵
  • $‘W:=\{\vec{w},\vec{u},\vec{v}\}‘$，即变量矩阵
  • $‘S^{\delta }:=‘$ 轮换置换后得到的位置集合，来自于Wiring
• Wiring(Copy Constraints)

  • 分析：Wiring即将离散的门连接起来，即某一个门的输出引脚要接入另一个门的输入引脚$‘⟺‘$约束变量矩阵$W$中某几个位置的元素是相等的$‘⟺‘$这一个元素出现在$‘W‘$矩阵的多个位置处

  • Wiring实现思路：

    • 把$‘W‘$矩阵中的每一个位置从1到3n进行唯一编号，则所有的编号构成一个位置集合$‘S‘$，将位置集合$S$对应的元素取出构成一个multiset $‘S_e‘$
    • 把每个元素出现在$W$中的位置编号取出放在一个集合中$‘s‘$，即一个元素对应一个位置集合$‘s‘$。将位置集合对应的元素取出构成一个multiset $‘s_e‘$。所有元素的$s$的并集即为$‘S‘$，$‘s_e‘$的并集为 $‘S_e‘$
    • $‘\forall s‘$，要使得 $‘s_e‘$中元素全部相等

    $‘⟺‘$ $‘\forall s_e‘$， $‘s_e‘$与其进行轮换置换$‘\delta ‘$后得到的集合$‘s_e^{\delta }‘$在Multiset的意义上是等价的

    $‘⟺‘$ $‘\forall s_e‘$， $‘\overrightarrow{s_e}+\vec{s}‘$与$‘\overrightarrow{s_e}+\overrightarrow{s^{\sigma }}‘$在Multiset的意义上是等价的

    $‘\Leftarrow ‘$令$‘S‘$为所有$‘s‘$的并集，$‘S^{\sigma }‘$为所有$‘s^{\sigma }‘$的并集，$‘S_e‘$为所有$‘s_e‘$的并集， $‘\overrightarrow{S_e}+\vec{S}‘$与$‘\overrightarrow{S_e}+\overrightarrow{S^{\sigma }}‘$在Multiset的意义上是等价的

    $‘⟺$令$\vec{T}=\overrightarrow{S_e}+\vec{S},\overrightarrow{T^{\sigma }}=\overrightarrow{S_e}+\overrightarrow{S^{\sigma }}‘$，取随机数$‘\gamma ‘$，有

    $‘(\gamma -t_0)(\gamma -t_1)\dots (\gamma -t_{n-1})=(\gamma -t_0^{\sigma })(\gamma -t_1^{\sigma })\dots (\gamma -t_{n-1}^{\sigma })‘$

    $‘即\prod _{i\in [n]}(\gamma -t_i)=\prod _{i\in [n]}(\gamma -t_i^{\sigma })‘$

    $‘即\prod _{i\in [n]}\frac{(\gamma -t_i)}{(\gamma -t_i^{\sigma })}=1‘$

    • 至此，问题转化成如何证明连乘等式 $‘b_0\cdot b_1\cdot b_2\cdot \dots b_{n-1}=c‘$，即证明一个n步递归，

      • 初始值：$‘r_0=1‘$
      • 递归定义：$‘r_i=r_{i-1}\cdot b_{i-1}‘$
      • 终止条件：$‘r_n=c‘$

      则有

      $$\begin{gathered} ‘b_0\cdot b_1\cdot b_2\cdot \dots b_{n-1}=c \\ ⟺r_0=1,r_i=r_{i-1}\cdot b_{i-1}，r_n=c‘ \end{gathered}$$

      所有$‘r_i‘$ 构成向量 $‘\vec{r}‘$

      • 至此，Wiring转化成三个约束

        • $‘r_0=1和r_n=c‘$ 即约束向量的指定位的值为k，即约束$‘\vec{r}‘$的第1位($‘r_0‘$)的值为1，第n+1位($‘r_n‘$)的值为$‘c‘$。

          设$‘e_i‘$为n维向量空间的标准基的第i个基向量，向量$‘\vec{r}‘$的第$‘i‘$位为$‘k‘$等价于：$‘{\vec{e}}_i\circ \vec{r}=k\times {\vec{e}}_i‘$

        • $‘r_i=r_{i-1}\cdot b_{i-1}‘$

2.2 Constraints Merge

R1CS to QAP

• $‘Lemma1:‘$ 带有Hadamard product运算的n维向量的群$‘{\mathbb{M}}_n‘$，和带有乘法运算的在$H$上的最高项次数不大于n-1的单变量多项式$‘{\mathbb{H}}_p^{(\le n-1)}[X]‘$的群，映射：$‘h:{\mathbb{M}}_n\to {\mathbb{H}}_p^{(\le n-1)}‘$,令$‘L_i(X)为LagrangeBasis‘$，有$‘h(\vec{m})=⟨\vec{m},{\vec{L}}_i(X)⟩‘$，是群同态

• $‘Lemma2:由Lemma1，有‘$

  $‘W_{m\times n}\cdot \vec{a}=U_{m\times n}\cdot \vec{a}\circ V_{m\times n}\cdot \vec{a}‘$ $‘⟺\forall X\in H,⟨\overrightarrow{⟨\vec{w},{\vec{L}}_i(X)⟩},\vec{a}⟩=⟨\overrightarrow{⟨\vec{u},{\vec{L}}_i(X)⟩},\vec{a}⟩\cdot ⟨\overrightarrow{⟨\vec{v},{\vec{L}}_i(X)⟩},\vec{a}⟩‘$

• $‘Lemma3:令c(X)=⟨\overrightarrow{⟨\vec{w},{\vec{L}}_i(X)⟩},\vec{a}⟩,a(X)=⟨\overrightarrow{⟨\vec{u},{\vec{L}}_i(X)⟩},\vec{a}⟩，b(X)=⟨\overrightarrow{⟨\vec{v},{\vec{L}}_i(X)⟩},\vec{a}⟩,有‘$

  $‘\forall X\in H,c(X)=a(X)\cdot b(X)‘$ $$\begin{gathered} ‘⟺\forall X\in H,a(X)\cdot b(X)-c(X)=0 \\ ⟺f(X)=a(X)\cdot b(X)-c(X)=0以H为根，X\in F \\ ⟺f(X)能被z_H(X)=(X-h_0)(X-h_1)(X-h_2)\dots (X-h_{n-1})整除,h_i\in H‘ \end{gathered}$$

• 令$‘q(x)=f(X)/z_H(X)‘$, 至此，完成了从R1CS到QAP到转换

Plonkish Arithmetization to QAP

Plonkish Arithmetization包含两部分约束：

$‘\overrightarrow{q_O}\circ \vec{w}=\overrightarrow{q_L}\circ \vec{u}+\overrightarrow{q_R}\circ \vec{v}+\overrightarrow{q_M}\circ (\vec{u}\circ \vec{v})+\overrightarrow{q_C}‘$和$‘r_0=1,r_i=r_{i-1}\cdot b_{i-1}，r_n=c‘$

第一部分约束每个门是正确计算的，即所谓算术约束；第二部分约束门与门之间正确连接，即所谓复制约束。

首先来转换算术约束：

• $‘Lemma4:‘$带有加法的n维向量的群$‘{\mathbb{M}}_n‘$，和带有加法的在$H$上的最高项次数不大于n-1的单变量多项式$‘{\mathbb{H}}_p^{(\le n-1)}[X]‘$的群，映射：$‘h:{\mathbb{M}}_n\to {\mathbb{H}}_p^{(\le n-1)}‘$，令$‘L_i(X)为LagrangeBasis‘$，有$h(\vec m)= \langle \vec m,\vec L(X) \rangle$，是群同态-$Lemma5:$同态映射的复合映射必定是同态映射-$由Lemma1,Lemma4,Lemma5,有\vec{q_O}\circ \vec{w}=\vec{q_L}\circ\vec{u}+\vec{q_R}\circ\vec{v}+\vec{q_M}\circ(\vec{u}\circ\vec{v})+\vec{q_C}\circ\vec{c} \\ \iff \langle \vec q_O,\vec L(X) \rangle \cdot \langle \vec w,\vec L(X) \rangle=\langle \vec q_L,\vec L(X) \rangle \cdot \langle \vec u,\vec L(X) \rangle+\langle \vec q_R,\vec L(X) \rangle \cdot \langle \vec v,\vec L(X) \rangle+\langle \vec q_m,\vec L(X) \rangle \cdot (\langle \vec u,\vec L(X) \rangle\cdot\langle \vec v,\vec L(X) \rangle )+\langle \vec q_C,\vec L(X) \rangle $令$a(X) =\langle \vec a,\vec L(X) \rangle$，上式转化为：$q_O(X)w(X)=q_L(X)u(X)+q_R(X)v(X)+q_M(X)u(X)v(X)+q_C(X)$-至此，n个算术约束转化成了一个由八个n-1次多项式之间构成的约束。\ast \ast 接着转换复制约束：\ast \ast -由$Lemma1$，有$\vec e_i \circ \vec r=k\times \vec e_i \\ \iff L_i(X)r(X)=k\times L_i(X) \\ \iff L_i(X)(r(X)-k)=0$有$r_0=1 \iff L_0(X)(r(X)-1)=0 \\ r_n=c \iff L_n(X)(r(X)-c)=0 $-令$L_i(X)$为定义在乘法子群$H$上的$Lagrange Basis$，由$Lemma1$,有$\vec r_{i}=\vec r_{i-1} \circ \vec b_{i-1} \\ \iff \langle \vec r,\vec L(\omega \cdot X) \rangle =\langle \vec r,\vec L(X) \rangle \cdot \langle \vec b,\vec L(X) \rangle

• 至此，复制约束转换成了三个多项式约束。

2.3 A function commitment scheme

在2.3中得到了一系列多项式之间的约束，本节我们来看如何实现多项式约束，

令：

\mathcal F:=function\ family$，即一类多项式$\mathbb F_p:= 有限域

对于\mathcal F$的CommitmentShceme框架如下：-$setup(\lambda) \to pp$计算publicparameter-$commit(pp,f,r) \to com_f基于随机数r对f\in \mathcal F的承诺$-$eval(prover \ P,verifier\ V)$对于给定的$com_f$，以及$x\in X,y\in Y:证明f(x)=y,即所谓的将f在点(x,y)处打开$-$P(pp,f,x,y,r) \to 简短证明\pi$-$V(pp,com_f,x,y,\pi)\to 接受/拒绝

三类典型的Function Family Commiments

• Polynominal commitments：次数不大于d的单变量多项式承诺 f(X)\in \mathbb F_p^{(\leq d)} [X]$-Multilinearcommitments：次数小于等于1的多变量多项式承诺$f(X_1,...,X_k)\in \mathbb F_p^{(\leq 1)}[X_1,...,X_K]$-Linearcommitments：$f_{\vec v}(\vec u)= \left \langle \vec u, \vec v \right \rangle=\sum _{i=1}^nu_iv_i

这三者从上到下，越来越general

PCS: Polynominal Commitment Scheme

适用于次数不大于d的单变量多项式 f(X)\in \mathbb F_p^{(\leq d)} [X]

Some usual PSC

• Bulletproofs：基于椭圆曲线，verifier的算法复杂度与d成线性相关
• KZG‘10，Dory’20：基于双线性椭圆曲线
• Dark’20：基于阶未知的群
• FRI：基于hash Function

KZG poly-commit scheme

• 预备知识：阶为p的群\ \mathbb G:=\{1,G,2\cdot G,3\cdot G,...,(p-1)\cdot G\} ,其中，G为生成元$-$setup(\lambda) \to pp$-取随机数$\alpha\in \mathbb F_p$-$pp=(H_0=1,H_1=\alpha \cdot G,H_2=\alpha^2 \cdot G,...,H_d=\alpha^d \cdot G)\in \mathbb G^{d+1}$-删除$\alpha$，$\alpha$也称为Godkey，即除了上帝，$\alpha$不能被任何人知道-$commit(pp,f,r) \to com_f$-$com_f:=f(\alpha)\cdot G \in \mathbb G$：具体的计算方法如下：$f(X)=f_0+f_1X+...+f_dX^d\implies com_f=f_0\cdot 1+f_1\cdot\alpha G+f_2\cdot\alpha^2 G+ ...+f_d\cdot \alpha^dG\iff com_f=f_0\cdot H——1+f_1\cdot H1+...+f_d\cdot H_d$-注意，此处是Binding的，但由于未做随机处理，故不是Hiding的，若需Hiding，需要extend-$eval(prover \ P,verifier\ V)$-目标：证明$f(u)=vf(u)=v\iff u是 \hat f =f-v的根\iff (X-u)整除\hat f\iff \exists q\in \mathbb{F}_p[X]\ \ s.t.\ \ q(X)\cdot(X-u)=f(X)-v$-$Prover(pp,f,u,v)$计算$商多项式q(X) 及其承诺com_q$，发送给Verifier-$Verifier(pp,com_f,u,v)$检查$(\alpha-u)\cdot com_q=com_f-v\cdot G$是否成立-此处的问题是$\alpha$是不可知的，那如何在不用显式地知道$\alpha$的前提下验证等式$(\alpha-u)\cdot com_q=com_f-v\cdot G$呢？在$com_q和com_f$中我们通过setup步骤将$\alpha$隐藏了，那么等式左侧的$(\alpha-u)$是不是同样也可以通过setup隐藏起来？为达到这个目的，我们需要扩展setup成如下-$setup(\lambda) \to pp$-取随机数$\alpha\in \mathbb F_p$-$pp=(H_0=1,H_1=\alpha \cdot G,H_2=\alpha^2 \cdot G,...,H_d=\alpha^d \cdot G)\in \mathbb G^{d+1} + (T_0=1,T_1=\alpha \cdot G_2) \in \mathbb G_2^1$，-删除$\alpha$，$\alpha$也称为Godkey，即除了上帝，$\alpha$不能被任何人知道-$Verifier(pp,com_f,u,v)$-引入双线性映射关系$e\in \mathbb G \times \mathbb G_2 \to \mathbb G_X$ - 至此，将原来需要验证的$‘(\alpha -u)\cdot co{m}_q\stackrel{?}{=}co{m}_f-v\cdot G‘$，转换成了 在$‘{\mathbb{G}}_X‘$上验证$‘e(co{m}_q,T_1-u\cdot T_0)\stackrel{?}{=}e(co{m}_f-v\cdot G,T_0)‘$

2.4 Polynominal IOP

Useful Lemma

• Lemma1: Schwartz zipple定理

• Lemma2: 单位根和乘法子群**：**

  令$‘\omega \in {\mathbb{F}}_p‘$为k次单位根，即 $‘{\omega }^k=1‘$

  乘法子群 $‘H:=\{1,\omega ,{\omega }^2,\dots ,{\omega }^{k-1}\}\subseteq {\mathbb{F}}_p‘$

  由于单位根的对称性，有$‘\prod _{i=0}^{k-1}(X-{\omega }^i)=X^k-1‘$

• Lemma3: $‘H‘$中的元素$‘{\omega }^i‘$均为$‘f‘$的根，即$‘f在H上均为0‘$ $‘⟺‘$ $‘f(x)能被\prod _{i=0}^{k-1}(X-{\omega }^i)整除‘$ $‘⟺‘$ $‘f(x)能被X^k-1整除‘$

  $‘⟺‘$存在商多项式 $‘q(X)=f(X)/(X^k-1)‘$

Poly-IOP可以高效完成的任务

• Task1 zero-test：证明$f$在H上等于0，即证明H中的元素均为$f$的根
• Task2 sum-check：证明$‘{\sum }_{a\in H}f(a)=b‘$，即证明$f$在H上全部取值的和等于b
• Task3 prod-check：证明$‘{\prod }_{a\in H}f(a)=c‘$，即证明$f$在H上全部取值的和等于c

Zero Test on H

1. Prover 向 Verifier Commit $‘f(X)和q(X),即Co{m}_f,Co{m}_q‘$
2. Verifier 向Prover 发送随机数r
3. Verifier 检查$‘f(r)\stackrel{?}{=}q(r)\cdot (r^k-1)‘$

参考资料

https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-arithmetization.md

https://www.youtube.com/watch?v=J4pVTamUBvU&list=PLj80z0cJm8QErn3akRcqvxUsyXWC81OGq&index=2

https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-polycom.md ](https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md)https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md](https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md)https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md